/**
 * 
 */
package tree.passed2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import tree.Node;

/**
 * @author xyyi
 *
 */
public class ValidateBinarySearchTree {

	/**
	Given a binary tree, determine if it is a valid binary search tree (BST).

	Assume a BST is defined as follows:

	The left subtree of a node contains only nodes with keys less than the node's key.
	The right subtree of a node contains only nodes with keys greater than the node's key.
	Both the left and right subtrees must also be binary search trees.
	 */
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
        
    }
	public boolean isValidBSTHelper(TreeNode root, long min, long max) {
		if (root == null)
			return true;

		return root.val > min && root.val < max
				&& isValidBSTHelper(root.left, min, root.val)
				&& isValidBSTHelper(root.right, root.val, max);
	}
	
	
	
	/*
	Not work for [Integer.MIN_VALUE, Integer.MIN_VALUE]
	public boolean isValidBST(TreeNode root) {
		return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	public boolean isValidBSTHelper(TreeNode root, int min, int max) {
		if (root == null)
			return true;

		// "=" for val is MIN_INT or MAX_INT
		return root.val >= min && root.val <= max
				&& isValidBSTHelper(root.left, min, root.val - 1)
				&& isValidBSTHelper(root.right, root.val + 1, max);
	}
	*/
	
    public boolean isValidBSTRInOrder(TreeNode root) {
    	if (root == null)
    		return true;
        List<TreeNode> list = new ArrayList<>();
        inOrder(root, list);
        int first = list.get(0).val;
        for (int i = 1; i < list.size(); i++) {
        	int second = list.get(i).val;
        	if (second <= first)
        		return false;
        	first = second;
        }
        
        return true;
    }
    
    private void inOrder(TreeNode root, List<TreeNode> list) {
    	if (root == null)
    		return;
    	inOrder(root.left, list);
    	list.add(root);
    	inOrder(root.right, list);
    }

	// pre order, time O(n), space O(lgn)
	public static boolean validateIterativePO(Node<Integer> root, int minValue,
			int maxValue) {
		if (root == null)
			return true;

		Stack<Node<Integer>> s = new Stack<Node<Integer>>();
		Stack<Integer> maxs = new Stack<Integer>();
		Stack<Integer> mins = new Stack<Integer>();
		s.add(root);
		maxs.add(maxValue);
		mins.add(minValue);
		while (!s.isEmpty()) {
			Node<Integer> node = s.pop();
			int max = maxs.pop();
			int min = mins.pop();
			if (node.value <= max && node.value >= min) {
				if (node.right != null) {
					s.push(node.right);
					mins.push(node.value + 1);
					maxs.push(max);
				}
				if (node.left != null) {
					s.push(node.left);
					mins.push(min);
					maxs.push(node.value - 1);
				}
			} else
				return false;
		}
		return true;
	}

	// level order, time O(n), space O(n)
	public static boolean validateIterativeIO(Node<Integer> root, int minValue,
			int maxValue) {
		if (null == root)
			return true;
		Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
		Queue<Integer> mins = new LinkedList<Integer>();
		Queue<Integer> maxs = new LinkedList<Integer>();
		q.add(root);
		mins.add(minValue);
		maxs.add(maxValue);
		while (!q.isEmpty()) {
			Node<Integer> node = q.poll();
			int min = mins.poll();
			int max = maxs.poll();
			if (node.value >= min && node.value <= max) {
				if (node.left != null) {
					q.add(node.left);
					mins.add(min);
					maxs.add(node.value - 1);
				}
				if (node.right != null) {
					q.add(node.right);
					mins.add(node.value + 1);
					maxs.add(max);
				}
			} else
				return false;
		}
		return true;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public ValidateBinarySearchTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
